Perché l'elaborazione di un array ordinato è più veloce dell'elaborazione di un array non ordinato?

Sei vittima del fallimento della previsione del ramo.
Che cos'è la previsione dei rami?
Considera un nodo ferroviario:
Immagine di Mecanismo, tramite Wikimedia Commons. Utilizzato con la licenza CC-By-SA 3.0.
Ora, per amor di discussione, supponiamo che questo sia indietro nel 1800, prima delle comunicazioni radio o a lunga distanza.
Sei l'operatore di un incrocio e senti arrivare un treno. Non hai idea di dove debba andare. Fermate il treno per chiedere all'autista quale direzione vuole. E poi si imposta l'interruttore in modo appropriato.
I treni sono pesanti e hanno molta inerzia. Quindi impiegano un'eternità per avviarsi e rallentare.
Esiste un modo migliore? Indovina in quale direzione andrà il treno!
Se hai indovinato, continua.
Se hai indovinato, il capitano si fermerà, indietreggierà e ti urlerà di premere l'interruttore. Quindi può riavviare l'altro percorso.
Se indovini ogni volta, il treno non dovrà mai fermarsi. Se indovini troppo spesso, il treno impiegherà molto tempo a fermarsi, tornare indietro e riavviarsi.
Considera un'istruzione if: a livello di processore, è un'istruzione di ramo:
Sei un processore e vedi un ramo. Non hai idea di come andrà. cosa fai? Interrompi l'esecuzione e attendi fino al completamento delle istruzioni precedenti. Quindi prosegui lungo il percorso corretto.
I processori moderni sono complicati e hanno lunghe condutture. Quindi impiegano un'eternità per "riscaldarsi" e "rallentare".
Esiste un modo migliore? Indovina in quale direzione andrà il ramo!
Se hai indovinato, continua l'esecuzione.
Se hai indovinato, devi svuotare la tubazione e tornare al ramo. Quindi puoi riavviare l'altro percorso.
Se indovini ogni volta, l'esecuzione non dovrà mai interrompersi. Se indovini troppo spesso, passi molto tempo a fermarti, tornare indietro e riavviare.
Questa è la previsione dei rami. Ammetto che non è la migliore analogia poiché il treno potrebbe semplicemente segnalare la direzione con una bandiera. Ma nei computer, il processore non sa in quale direzione andrà un ramo fino all'ultimo momento.
Quindi come immagineresti strategicamente di ridurre al minimo il numero di volte in cui il treno deve tornare indietro e scendere sull'altro percorso? Guardi la storia passata! Se il treno va a sinistra il 99% delle volte, allora indovini a sinistra. Se si alterna, alterna le tue ipotesi. Se va in un modo ogni tre volte, indovina lo stesso ...
In altre parole, cerchi di identificare uno schema e di seguirlo. Questo è più o meno il modo in cui funzionano i predittori di ramo.
La maggior parte delle applicazioni ha rami ben educati. Pertanto, i predittori delle filiali moderne raggiungeranno in genere tassi di successo> 90%. Ma di fronte a rami imprevedibili senza schemi riconoscibili, i predittori di rami sono praticamente inutili.
Ulteriori letture: articolo "Ramo predittore" su Wikipedia.
Come accennato sopra, il colpevole è questa istruzione if:
if (dati [c]> = 128)
somma + = dati [c];
Si noti che i dati sono distribuiti uniformemente tra 0 e 255. Quando i dati vengono ordinati, all'incirca la prima metà delle iterazioni non entrerà nell'istruzione if. Dopodiché, inseriranno tutti l'istruzione if.
Questo è molto amichevole per il predittore del ramo poiché il ramo va consecutivamente nella stessa direzione molte volte. Anche un semplice contatore di saturazione predice correttamente il ramo tranne per le poche iterazioni dopo che ha cambiato direzione.
Visualizzazione rapida:
T = ramo preso
N = ramo non preso
dati [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
ramo = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (facile da prevedere)
Tuttavia, quando i dati sono completamente casuali, il predittore di ramo viene reso inutilizzabile, perché non può prevedere dati casuali. Quindi ci sarà probabilmente circa il 50% di previsioni errate (non meglio di ipotesi casuali).
dati [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
ramo = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (completamente casuale - difficile da prevedere)
Allora cosa si può fare?
Se il compilatore non è in grado di ottimizzare il ramo in una mossa condizionale, puoi provare alcuni hack se sei disposto a sacrificare la leggibilità per le prestazioni.
Sostituire:
if (dati [c]> = 128)
somma + = dati [c];
con:
int t = (dati [c] - 128) >> 31;
somma + = ~ t & dati [c];
Questo elimina il ramo e lo sostituisce con alcune operazioni bit per bit.
(Nota che questo hack non è strettamente equivalente all'istruzione if originale. Ma in questo caso, è valido per tutti i valori di input di data [].)
Benchmark: Core i7 920 da 3,5 GHz
C ++ - Visual Studio 2010 - versione x64
// Branch - Random
secondi = 11,777
// Branch - Sorted
secondi = 2,352
// Branchless - Random
secondi = 2,564
// Branchless - Ordinato
secondi = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Branch - Random
secondi = 10,93293813
// Branch - Sorted
secondi = 5,643797077
// Branchless -Casuale
secondi = 3,113581453
// Branchless - Ordinato
secondi = 3,186068823
Osservazioni:
Con il ramo: c'è un'enorme differenza tra i dati ordinati e non ordinati.
Con l'hack: non c'è differenza tra dati ordinati e non ordinati.
Nel caso C ++, l'hack è in realtà un po 'più lento rispetto al ramo quando i dati vengono ordinati.
Una regola pratica generale consiste nell'evitare ramificazioni dipendenti dai dati nei cicli critici (come in questo esempio).
Aggiornare:
GCC 4.6.1 con -O3 o -ftree-vectorize su x64 è in grado di generare una mossa condizionale. Quindi non c'è differenza tra i dati ordinati e non ordinati: entrambi sono veloci.
(O piuttosto veloce: per il caso già ordinato, cmov può essere più lento soprattutto se GCC lo mette sul percorso critico invece di aggiungerlo semplicemente, specialmente su Intel prima di Broadwell dove cmov ha una latenza di 2 cicli: il flag di ottimizzazione gcc -O3 rende il codice più lento di -O2)
VC ++ 2010 non è in grado di generare mosse condizionali per questo ramo anche in / Ox.
Intel C ++ Compiler (ICC) 11 fa qualcosa di miracoloso. Scambia i due anelli, sollevando così il ramo imprevedibile sull'anello esterno. Quindi non solo è immune alle previsioni errate, ma è anche due volte più veloce di qualsiasi cosa VC ++ e GCC possano generare! In altre parole, ICC ha approfittato del ciclo di test per sconfiggere il benchmark ...
Se date al compilatore Intel il codice branchless, esso lo vettorializza appena a destra ... ed è altrettanto veloce come con il branch (con lo scambio di loop).
Questo dimostra che anche i compilatori moderni maturi possono variare enormemente nella loro capacità di ottimizzare il codice ...
|
Previsione dei rami.
Con un array ordinato, i dati della condizione [c]> = 128 sono inizialmente falsi per una serie di valori, quindi diventano veri per tutti i valori successivi. È facile da prevedere. Con un array non ordinato, paghi il costo di ramificazione.
|
Il motivo per cui le prestazioni migliorano drasticamente quando i dati vengono ordinati è che la penalità di previsione del ramo viene rimossa, come spiegato magnificamente nella risposta di Mysticial.
Ora, se guardiamo il codice
if (dati [c]> = 128)
somma + = dati [c];
possiamo scoprire che il significato di questo particolare ramo if ... else ... è aggiungere qualcosa quando una condizione è soddisfatta. Questo tipo di ramo può essere facilmente trasformato in un'istruzione di spostamento condizionale, che verrebbe compilata in un'istruzione di spostamento condizionale: cmovl, in un sistema x86. Il ramo e quindi la potenziale penalità di previsione del ramo viene rimosso.
In C, quindi C ++, l'istruzione, che verrebbe compilata direttamente (senza alcuna ottimizzazione) nell'istruzione di spostamento condizionale in x86, è l'operatore ternario ...? ...: .... Quindi riscriviamo l'affermazione sopra in una equivalente:
somma + = dati [c]> = 128? dati [c]: 0;
Pur mantenendo la leggibilità, possiamo controllare il fattore di accelerazione.
Su un Intel Core i7-2600K a 3,4 GHz e modalità di rilascio di Visual Studio 2010, il benchmark è (formato copiato da Mysticial):
x86
// Branch - Random
secondi = 8,885
// Branch - Sorted
secondi = 1,528
// Branchless - Random
secondi = 3,716
// Branchless - Ordinato
secondi = 3,71
x64
// Branch - Random
secondi = 11,302
// Branch - Sorted
secondi = 1.830
// Branchless - Random
secondi = 2,736
// Branchless - Ordinato
secondi = 2,737
Il risultato è robusto in più test. Otteniamo una grande velocità quando il risultato del ramo è imprevedibile, ma soffriamo un po 'quando è prevedibile. In effetti, quando si utilizza uno spostamento condizionale, le prestazioni sono le stesse indipendentemente dal modello di dati.
Ora guardiamo più da vicino esaminando l'assembly x86 che generano. Per semplicità, utilizziamo due funzioni max1 e max2.
max1 usa il ramo condizionale se ... altrimenti ...:
int max1 (int a, int b) {
se (a> b)
return a;
altro
ritorno b;
}
max2 utilizza l'operatore ternario ...? ...: ...:
int max2 (int a, int b) {
restituire a> b? a: b;
}
Su una macchina x86-64, GCC -S genera l'assembly seguente.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
partire
ret
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
partire
ret
max2 utilizza molto meno codice a causa dell'utilizzo delle istruzioni cmovge. Ma il vero guadagno è che max2 non implica salti di ramo, jmp, che avrebbero una significativa penalizzazione delle prestazioni se il risultato previsto non fosse corretto.
Allora perché una mossa condizionale funziona meglio?
In un tipico processore x86, l'esecuzione di un'istruzione è suddivisa in più fasi. Approssimativamente, abbiamo hardware diverso per affrontare fasi diverse. Quindi non dobbiamo aspettare che finisca un'istruzione per iniziarne una nuova. Questo si chiama pipelining.
In un caso di ramo, la seguente istruzione è determinata dalla precedente, quindi non possiamo eseguire il pipelining. Dobbiamo aspettare o prevedere.
In un caso di spostamento condizionale,l'istruzione di movimento condizionale di esecuzione è suddivisa in più fasi, ma le fasi precedenti come Fetch e Decode non dipendono dal risultato dell'istruzione precedente; solo le ultime fasi richiedono il risultato. Pertanto, attendiamo una frazione del tempo di esecuzione di un'istruzione. Questo è il motivo per cui la versione dello spostamento condizionale è più lenta del ramo quando la previsione è facile.
Il libro Computer Systems: A Programmer's Perspective, seconda edizione, lo spiega in dettaglio. È possibile controllare la Sezione 3.6.6 per le istruzioni di spostamento condizionale, l'intero capitolo 4 per l'architettura del processore e la sezione 5.11.2 per un trattamento speciale per le previsioni di branch e le penalità per errori di previsione.
A volte, alcuni compilatori moderni possono ottimizzare il nostro codice in assembly con prestazioni migliori, a volte alcuni compilatori non possono (il codice in questione utilizza il compilatore nativo di Visual Studio). Conoscere la differenza di prestazioni tra un ramo e uno spostamento condizionale quando è imprevedibile può aiutarci a scrivere codice con prestazioni migliori quando lo scenario diventa così complesso che il compilatore non può ottimizzarli automaticamente.
|
Se sei curioso di ulteriori ottimizzazioni che possono essere apportate a questo codice, considera questo:
A partire dal ciclo originale:
for (unsigned i = 0; i <100000; ++ i)
{
for (unsigned j = 0; j  = 128)
somma + = dati [j];
}
}
Con lo scambio di loop, possiamo tranquillamente cambiare questo loop in:
for (unsigned j = 0; j  = 128)
somma + = dati [j];
}
}
Quindi, puoi vedere che il condizionale if è costante durante l'esecuzione del ciclo i, quindi puoi sollevare il if out:
for (unsigned j = 0; j  = 128)
{
for (unsigned i = 0; i <100000; ++ i)
{
somma + = dati [j];
}
}
}
Quindi, vedi che il ciclo interno può essere compresso in una singola espressione, assumendo che il modello a virgola mobile lo consenta (/ fp: fast viene lanciato, ad esempio)
for (unsigned j = 0; j  = 128)
{
somma + = dati [j] * 100000;
}
}
Quello è 100.000 volte più veloce di prima.
|
Senza dubbio alcuni di noi sarebbero interessati a metodi per identificare il codice che è problematico per il predittore di ramo della CPU. Lo strumento Valgrind cachegrind ha un simulatore di predittori di rami, abilitato utilizzando il flag --branch-sim = yes. Eseguendolo sugli esempi in questa domanda, con il numero di cicli esterni ridotto a 10000 e compilato con g ++, si ottengono questi risultati:
Smistato:
== 32551 == Filiali: 656.645.130 (656.609.208 cond + 35.922 ind)
== 32551 == Errori di previsione: 169.556 (169.095 cond + 461 ind)
== 32551 == Tasso errato: 0,0% (0,0% + 1,2%)
Indifferenziato:
== 32555 == Filiali: 655.996.082 (655.960.160 cond + 35.922 ind)
== 32555 == Errori di previsione: 164.073.152 (164.072.692 cond + 460 ind)
== 32555 == Tasso errato: 25,0% (25,0% + 1,2%)
Analizzando l'output riga per riga prodotto da cg_annotate, vediamo per il ciclo in questione:
Smistato:
Bc Bcm Bi Bim
10.001 4 0 0 per (senza segno i = 0; i <10000; ++ i)
. . . . {
. . . . // ciclo primario
327.690.000 10.016 0 0 per (unsigned c = 0; c  = 128)
0 0 0 0 somma + = dati [c];
. . . . }
. . . . }
Indifferenziato:
Bc Bcm Bi Bim
10.001 4 0 0 per (senza segno i = 0; i <10000; ++ i)
. . . . {
. . . . // ciclo primario
327.690.000 10.038 0 0 per (unsigned c = 0; c  = 128)
0 0 0 0 somma + = dati [c];
. . . . }
. . . . }
Ciò consente di identificare facilmente la riga problematica: nella versione non ordinata la riga if (data [c]> = 128) causa 164.050.007 rami condizionali non previsti (Bcm) nel modello di previsione dei rami di cachegrind, mentre ne causa solo 10.006 nella versione ordinata .
In alternativa, su Linux è possibile utilizzare il sottosistema dei contatori delle prestazioni per eseguire la stessa operazione, ma con prestazioni native utilizzando i contatori della CPU.
perf stat ./sumtest_sorted
Smistato:
Statistiche contatore delle prestazioni per "./sumtest_sorted":
11808.095776 task-clock # 0.998 CPU utilizzate
1.062 selettori di contesto # 0,090 K / sec
14 migrazioni CPU # 0,001 K / sec
337 page-fault # 0,029 K / sec
26.487.882.764 cicli # 2.243 GHz
41.025.654.322 istruzioni # 1.55 insns per ciclo
6.558.871.379 filiali # 555.455 M / sec
567.204 filiali perse # 0,01% di tutte le filiali
11,827228330 secondi di tempo trascorsi
Indifferenziato:
Prestazionestatistiche contatore per "./sumtest_unsorted":
28877.954344 task-clock # 0.998 CPU utilizzate
2.584 selettori di contesto # 0,089 K / sec
18 migrazioni CPU # 0,001 K / sec
335 page-fault # 0,012 K / sec
65.076.127.595 cicli # 2.253 GHz
41.032.528.741 istruzioni # 0,63 insns per ciclo
6.560.579.013 filiali # 227.183 M / sec
1.646.394.749 filiali perse # 25,10% di tutte le filiali
28,935500947 secondi di tempo trascorsi
Può anche eseguire l'annotazione del codice sorgente con il disassemblaggio.
record perf -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
Percentuale | Codice sorgente e disassemblaggio di sumtest_unsorted
------------------------------------------------
...
: somma + = dati [c];
0.00: 400a1a: mov -0x14 (% rbp),% eax
39.97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4.60: 400a26: cltq
0.00: 400a28: aggiungi% rax, -0x30 (% rbp)
...
Vedere il tutorial sulle prestazioni per maggiori dettagli.
|
Ho appena letto su questa domanda e le sue risposte, e sento che manca una risposta.
Un modo comune per eliminare la previsione dei rami che ho riscontrato funzionare particolarmente bene nei linguaggi gestiti è una ricerca nella tabella invece di utilizzare un ramo (anche se in questo caso non l'ho testato).
Questo approccio funziona in generale se:
è un piccolo tavolo ed è probabile che venga memorizzato nella cache del processore e
stai eseguendo le cose in un ciclo abbastanza stretto e / o il processore può precaricare i dati.
Sfondo e perché
Dal punto di vista del processore, la tua memoria è lenta. Per compensare la differenza di velocità, un paio di cache sono integrate nel processore (cache L1 / L2). Quindi immagina di fare i tuoi bei calcoli e scopri che hai bisogno di un pezzo di memoria. Il processore eseguirà l'operazione di "caricamento" e caricherà la parte di memoria nella cache, quindi la utilizza per eseguire il resto dei calcoli. Poiché la memoria è relativamente lenta, questo "carico" rallenterà il programma.
Come la previsione dei rami, anche questa è stata ottimizzata nei processori Pentium: il processore prevede di dover caricare un dato e tenta di caricarlo nella cache prima che l'operazione raggiunga effettivamente la cache. Come abbiamo già visto, la previsione dei rami a volte va terribilmente sbagliata: nel peggiore dei casi è necessario tornare indietro e attendere effettivamente un carico di memoria, che richiederà un'eternità (in altre parole: la previsione del ramo fallita è cattiva, una memoria caricare dopo un errore di previsione del ramo è semplicemente orribile!).
Fortunatamente per noi, se il pattern di accesso alla memoria è prevedibile, il processore lo caricherà nella sua cache veloce e tutto va bene.
La prima cosa che dobbiamo sapere è cosa è piccolo? Mentre più piccolo è generalmente migliore, una regola pratica è di attenersi alle tabelle di ricerca di dimensioni <= 4096 byte. Come limite superiore: se la tua tabella di ricerca è più grande di 64 KB, probabilmente vale la pena riconsiderarla.
Costruire un tavolo
Quindi abbiamo capito che possiamo creare un tavolino. La prossima cosa da fare è installare una funzione di ricerca. Le funzioni di ricerca sono generalmente piccole funzioni che utilizzano un paio di operazioni di base su interi (and, or, xor, shift, add, remove e forse moltiplica). Vuoi che il tuo input sia tradotto dalla funzione di ricerca in una sorta di "chiave univoca" nella tua tabella, che poi ti dà semplicemente la risposta di tutto il lavoro che volevi che facesse.
In questo caso:> = 128 significa che possiamo mantenere il valore, <128 significa che ce ne sbarazziamo. Il modo più semplice per farlo è usare un 'AND': se lo conserviamo, lo facciamo AND con 7FFFFFFF; se vogliamo sbarazzarcene, lo facciamo AND con 0. Nota anche che 128 è una potenza di 2 - quindi possiamo andare avanti e creare una tabella di 32768/128 numeri interi e riempirla con uno zero e molti 7FFFFFFFF's.
Lingue gestite
Potresti chiederti perché funziona bene nelle lingue gestite. Dopotutto, le lingue gestite controllano i confini degli array con un ramo per assicurarsi di non sbagliare ...
Beh, non esattamente ... :-)
C'è stato un bel po 'di lavoro sull'eliminazione di questo ramo per i linguaggi gestiti. Per esempio:
for (int i = 0; i  = 128)? c: 0;
}
// Test
DateTime startTime = System.DateTime.Now;
somma lunga = 0;
for (int i = 0; i <100000; ++ i)
{
// Ciclo primario
for (int j = 0; j  = 128. Ciò significa che possiamo facilmente estrarre un singolo bit che ci dirà se vogliamo o meno un valore: spostando i dati a destra 7 bit, ci rimane uno 0 bit o un 1 bit, e vogliamo solo aggiungere il valore quando abbiamo 1 bit. Chiamiamo questo bit "bit decisionale".
Usando il valore 0/1 del bit decisionale come indice in un array, possiamo creare codice che sarà altrettanto veloce indipendentemente dal fatto che i dati siano ordinati o meno. Il nostro codice aggiungerà sempre un valore, ma quando il bit di decisione è 0, aggiungeremo il valore da qualche parte non ci interessa. Ecco il codice:
// Test
clock_t start = clock ();
lungo lungo a [] = {0, 0};
somma lunga lunga;
for (unsigned i = 0; i <100000; ++ i)
{
// Ciclo primario
for (unsigned c = 0; c > 7);
a [j] + = dati [c];
}
}
double elapsedTime = static_cast  (clock () - start) / CLOCKS_PER_SEC;
somma = a [1];
Questo codice spreca metà delle aggiunte ma non ha mai un errore di previsione del ramo. È tremendamente più veloce su dati casuali rispetto alla versione con un'istruzione if effettiva.
Ma nei miei test, una tabella di ricerca esplicita era leggermente più veloce di questa, probabilmente perché l'indicizzazione in una tabella di ricerca era leggermente più veloce dello spostamento di bit. Questo mostra come il mio codice imposta e utilizza la tabella di ricerca (chiamata senza fantasia lut per "Tabella di ricerca" nel codice). Ecco il codice C ++:
// Dichiara e quindi compila la tabella di ricerca
int lut [256];
for (unsigned c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Usa la tabella di ricerca dopo che è stata creata
for (unsigned i = 0; i <100000; ++ i)
{
// Ciclo primario
for (unsigned c = 0; c  valore)
node = node-> pLeft;
altro
node = node-> pRight;
questa libreria farebbe qualcosa di simile:
i = (x  valore);
nodo = nodo-> collegamento [i];
Ecco un collegamento a questo codice: Red Black Trees, Eternally Confuzzled
|
Nel caso ordinato, puoi fare di meglio che fare affidamento sulla previsione del ramo di successo o su qualsiasi trucco di confronto senza rami: rimuovere completamente il ramo.
Infatti, l'array è partizionato in una zona contigua con dati <128 e un'altra con dati> = 128. Quindi dovresti trovare il punto di partizione con una ricerca dicotomica (usando Lg (arraySize) = 15 confronti), quindi fare un accumulo diretto da quel punto.
Qualcosa come (deselezionato)
int i = 0, j, k = arraySize;
mentre (i > 1;
if (dati [j]> = 128)
k = j;
altro
i = j;
}
somma = 0;
for (; i > 1;
for (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
for (sum = 0; i  = 128)
/ \
/ \
/ \
vero falso
/ \
/ \
/ \
/ \
B) somma + = dati [c]; C) for loop o print ().
Senza la previsione del ramo, si verificherebbe quanto segue:
Per eseguire l'istruzione B o l'istruzione C il processore dovrà attendere che l'istruzione A non raggiunga lo stadio EX nella pipeline, poiché la decisione di passare all'istruzione B o all'istruzione C dipende dal risultato dell'istruzione A. Quindi la pipeline sarà simile a questo.
quando la condizione if ritorna vera:
Quando la condizione if restituisce false:
Come risultato dell'attesa del risultato dell'istruzione A, il totale dei cicli della CPU spesi nel caso precedente (senza predizione del ramo; sia vero che falso) è 7.
Allora, qual è la previsione dei rami?
Il predittore di ramo proverà a indovinare in che direzione andrà un ramo (una struttura if-then-else) prima che questo sia noto per certo. Non aspetterà che l'istruzione A raggiunga lo stadio EX della pipeline, ma indovinerà la decisione e andrà a quell'istruzione (B o C nel caso del nostro esempio).
In caso di ipotesi corretta, la pipeline ha un aspetto simile a questo:
Se in seguito viene rilevato che l'ipotesi era sbagliata, le istruzioni parzialmente eseguite vengono scartate e la pipeline ricomincia con il ramo corretto, con un ritardo.
Il tempo sprecato in caso di previsione errata di un ramo è uguale al numero di fasi nella pipeline dalla fase di recupero alla fase di esecuzione. I microprocessori moderni tendono ad avere pipeline piuttosto lunghe in modo che il ritardo di previsione errata sia compreso tra 10 e 20 cicli di clock. Più lunga è la pipeline, maggiore è la necessità di un buon predittore di diramazione.
Nel codice dell'OP, la prima volta quando è condizionale, il predittore di ramo non ha alcuna informazione per basare la previsione, quindi la prima volta sceglierà in modo casuale l'istruzione successiva. Più avanti nel ciclo for, può basare la previsione sulla cronologia.
Per un array ordinato in ordine crescente, ci sono tre possibilità:
Tutti gli elementi sono inferiori a 128
Tutti gli elementi sono maggiori di 128
Alcuni nuovi elementi iniziali sono inferiori a 128 e successivamente diventano maggiori di 128
Supponiamo che il predittore assumerà sempre il ramo vero alla prima esecuzione.
Quindi, nel primo caso, ci vorrà sempre il veroramo poiché storicamente tutte le sue previsioni sono corrette.
Nel 2 ° caso, inizialmente predice sbagliato, ma dopo alcune iterazioni predice correttamente.
Nel 3 ° caso, inizialmente predice correttamente fino a quando gli elementi non sono inferiori a 128. Dopodiché fallirà per un po 'di tempo e si correggerà da solo quando vedrà il fallimento della previsione del ramo nella storia.
In tutti questi casi il guasto sarà di numero troppo inferiore e di conseguenza, solo poche volte sarà necessario scartare le istruzioni parzialmente eseguite e ricominciare con il ramo corretto, con conseguente minor numero di cicli della CPU.
Ma nel caso di un array casuale non ordinato, la previsione dovrà scartare le istruzioni parzialmente eseguite e ricominciare con il ramo corretto la maggior parte del tempo e produrre più cicli di CPU rispetto all'array ordinato.
|
Una risposta ufficiale sarebbe da
Intel: evitare il costo di previsioni errate della filiale
Intel - Riorganizzazione di branch e loop per evitare previsioni errate
Articoli scientifici - architettura del computer per la previsione dei rami
Libri: J.L. Hennessy, D.A. Patterson: Architettura del computer: un approccio quantitativo
Articoli su pubblicazioni scientifiche: T.Y. Sì, Y.N. Patt ha fatto molti di questi sulle previsioni dei rami.
Puoi anche vedere da questo delizioso diagramma perché il predittore di ramo viene confuso.
Ogni elemento nel codice originale è un valore casuale
dati [c] = std :: rand ()% 256;
quindi il predittore cambierà lato come il colpo std :: rand ().
D'altra parte, una volta ordinato, il predittore si sposterà prima in uno stato di fortemente non preso e quando i valori cambiano al valore alto il predittore in tre passaggi cambierà completamente da fortemente non preso a fortemente preso.
|
Nella stessa riga (penso che questo non sia stato evidenziato da nessuna risposta) è bene menzionare che a volte (specialmente nel software in cui le prestazioni contano, come nel kernel Linux) puoi trovare alcune istruzioni if ​​come le seguenti:
if (probabile (everything_is_ok))
{
/* Fare qualcosa */
}
o in modo simile:
if (improbabile (very_improbable_condition))
{
/* Fare qualcosa */
}
Sia probabile () che improbabile () sono infatti macro che vengono definite utilizzando qualcosa come __builtin_expect di GCC per aiutare il compilatore a inserire il codice di previsione per favorire la condizione tenendo conto delle informazioni fornite dall'utente. GCC supporta altri incorporati che potrebbero cambiare il comportamento del programma in esecuzione o emettere istruzioni di basso livello come svuotare la cache, ecc. Vedere questa documentazione che passa attraverso i integrati di GCC disponibili.
Normalmente questo tipo di ottimizzazioni si trovano principalmente in applicazioni hard-real time o sistemi embedded in cui il tempo di esecuzione è importante ed è fondamentale. Ad esempio, se stai verificando una condizione di errore che si verifica solo 1/10000000 volte, perché non informarne il compilatore? In questo modo, per impostazione predefinita, la previsione del ramo presuppone che la condizione sia falsa.
|
Le operazioni booleane usate di frequente in C ++ producono molti rami nel programma compilato. Se questi rami sono all'interno di loop e sono difficili da prevedere, possono rallentare notevolmente l'esecuzione. Le variabili booleane vengono memorizzate come numeri interi a 8 bit con il valore 0 per falso e 1 per vero.
Le variabili booleane sono sovradeterminate nel senso che tutti gli operatori che hanno variabili booleane come input controllano se gli input hanno un valore diverso da 0 o 1, ma gli operatori che hanno booleani come output non possono produrre nessun altro valore che 0 o 1. Ciò effettua operazioni con Variabili booleane come input meno efficienti del necessario.
Considera l'esempio:
bool a, b, c, d;
c = a && b;
d = a || b;
Questo è tipicamente implementato dal compilatore nel modo seguente:
bool a, b, c, d;
if (a! = 0) {
if (b! = 0) {
c = 1;
}
altro {
goto CFALSE;
}
}
altro {
CFALSE:
c = 0;
}
if (a == 0) {
if (b == 0) {
d = 0;
}
altro {
goto DTRUE;
}
}
altro {
DTRUE:
d = 1;
}
Questo codice è tutt'altro che ottimale. I rami possono richiedere molto tempo in caso di previsioni errate. Le operazioni booleane possono essere rese molto più efficienti se si sa con certezza che gli operandi non hanno valori diversi da 0 e 1. Il motivo per cui il compilatore non assume tale assunto è che le variabili potrebbero avere altri valori se non sono inizializzate o provengono da fonti sconosciute. Il codice precedente può essere ottimizzato se aeb è stato inizializzato su valori validi o se provengono da operatori che producono output booleano. Il codice ottimizzato ha questo aspetto:
char a = 0, b = 1, c, d;
c = a & b;
d = a | b;
char viene utilizzato al posto di bool per rendere possibile l'uso degli operatori bit per bit (& e |) invece degli operatori booleani (&& e ||). Gli operatori bit per bit sono istruzioni singole che richiedono un solo ciclo di clock. L'operatore OR (|) funziona anche se aeb hanno valori diversi da 0 o 1. L'operatore AND (&) e l'operatore OR ESCLUSIVO (^) possono fornire risultati incoerenti se gli operandi hanno valori diversi da 0 e 1.
~ non può essere utilizzato per NOT. Anziché,puoi creare un NOT booleano su una variabile nota come 0 o 1 XOR con 1:
bool a, b;
b =! a;
può essere ottimizzato per:
char a = 0, b;
b = a ^ 1;
a && b non può essere sostituito con a & b se b è un'espressione che non dovrebbe essere valutata se a è falso (&& non valuterà b, & lo farà). Allo stesso modo, un || b non può essere sostituito con a | b se b è un'espressione che non dovrebbe essere valutata se a è vera.
L'utilizzo di operatori bit per bit è più vantaggioso se gli operandi sono variabili rispetto a se gli operandi sono confronti:
bool a; doppia x, y, z;
a = x> y && z <5.0;
è ottimale nella maggior parte dei casi (a meno che non ti aspetti che l'espressione && generi molte previsioni errate sui rami).
|
Certamente!...
La previsione dei rami rende la logica più lenta, a causa del cambio che avviene nel codice! È come se stessi percorrendo una strada dritta o una strada con molte svolte, di sicuro quella dritta verrà fatta più velocemente! ...
Se l'array è ordinato, la tua condizione è falsa al primo passaggio: data [c]> = 128, quindi diventa un valore vero per tutto il percorso fino alla fine della strada. È così che arrivi più velocemente alla fine della logica. D'altra parte, usando un array non ordinato, hai bisogno di molte svolte ed elaborazioni che rendono il tuo codice più lento di sicuro ...
Guarda l'immagine che ho creato per te qui sotto. Quale strada finirà più velocemente?
Quindi a livello di codice, la previsione dei rami fa sì che il processo sia più lento ...
Inoltre, alla fine, è bene sapere che abbiamo due tipi di previsioni di branch che ciascuno influenzerà il tuo codice in modo diverso:
1. Statico
2. Dinamico
La previsione dei rami statici viene utilizzata dal microprocessore per la prima volta
viene rilevato un ramo condizionale e la previsione del ramo dinamico
utilizzato per le successive esecuzioni del codice di diramazione condizionale.
Al fine di scrivere in modo efficace il tuo codice per trarne vantaggio
regole, quando scrivi if-else o switch, controlla di più
prima i casi comuni e procedono progressivamente fino ai meno comuni.
I loop non richiedono necessariamente un ordine speciale di codice per
previsione del ramo statico, come solo la condizione dell'iteratore del ciclo
è normalmente utilizzato.
|
Questa domanda ha già ricevuto una risposta eccellente molte volte. Tuttavia, vorrei attirare l'attenzione del gruppo su un'altra analisi interessante.
Recentemente questo esempio (leggermente modificato) è stato utilizzato anche come un modo per dimostrare come un pezzo di codice può essere profilato all'interno del programma stesso su Windows. Lungo la strada, l'autore mostra anche come utilizzare i risultati per determinare dove il codice trascorre la maggior parte del suo tempo sia nel caso ordinato che in quello non ordinato. Infine il pezzo mostra anche come utilizzare una caratteristica poco conosciuta dell'HAL (Hardware Abstraction Layer) per determinare la quantità di previsioni errate di branch che si verificano nel caso non ordinato.
Il link è qui:
Una dimostrazione di auto-profilazione
|
Come ciò che è già stato menzionato da altri, ciò che sta dietro il mistero è Branch Predictor.
Non sto cercando di aggiungere qualcosa ma di spiegare il concetto in un altro modo.
C'è una breve introduzione sul wiki che contiene testo e diagramma.
Mi piace la spiegazione di seguito che utilizza un diagramma per elaborare intuitivamente il Branch Predictor.
Nell'architettura del computer, un predittore di ramo è un file
circuito digitale che cerca di indovinare da che parte un ramo (ad es
if-then-else) andrà prima che questo sia noto per certo. Il
lo scopo del predittore di ramo è migliorare il flusso nel file
pipeline di istruzioni. I predittori di branch svolgono un ruolo fondamentale in
raggiungendo alte prestazioni efficaci in molte pipeline moderne
architetture a microprocessore come x86.
La ramificazione a due vie viene solitamente implementata con un salto condizionale
istruzione. Un salto condizionale può essere "non eseguito" e continuare
esecuzione con il primo ramo di codice che segue immediatamente
dopo il salto condizionale, oppure può essere "preso" e passare a un
posto diverso nella memoria del programma in cui si trova il secondo ramo del codice
immagazzinato. Non è noto con certezza se sarà un salto condizionale
preso o non preso fino a quando la condizione non è stata calcolata e il
il salto condizionale ha superato la fase di esecuzione nell'istruzione
tubazione (vedi fig.1).
Sulla base dello scenario descritto, ho scritto una demo di animazione per mostrare come le istruzioni vengono eseguite in una pipeline in diverse situazioni.
Senza Branch Predictor.
Senza la previsione del ramo, il processore dovrebbe attendere fino al
L'istruzione di salto condizionale ha superato la fase di esecuzione prima del
l'istruzione successiva può entrare nella fase di recupero nella pipeline.
L'esempio contiene tre istruzioni e la prima è un'istruzione di salto condizionale. Le ultime due istruzioni possono entrare nella pipeline finché non viene eseguita l'istruzione di salto condizionale.
Saranno necessari 9 cicli di clock per completare 3 istruzioni.
Usa Branch Predictor e non fare un salto condizionale. Supponiamo che la previsione non stia prendendo ilsalto condizionale.
Saranno necessari 7 cicli di clock per completare 3 istruzioni.
Usa Branch Predictor e fai un salto condizionale. Supponiamo che la previsione non stia eseguendo il salto condizionale.
Saranno necessari 9 cicli di clock per completare 3 istruzioni.
Il tempo sprecato in caso di previsione errata di una filiale è pari a
il numero di fasi nella pipeline dalla fase di recupero a
eseguire la fase. I microprocessori moderni tendono ad avere tempi piuttosto lunghi
pipeline in modo che il ritardo di previsione errata sia compreso tra 10 e 20 clock
cicli. Di conseguenza, allungare una pipeline aumenta la necessità di un file
predittore di ramo più avanzato.
Come puoi vedere, sembra che non abbiamo motivo per non utilizzare Branch Predictor.
È una demo abbastanza semplice che chiarisce la parte fondamentale di Branch Predictor. Se quelle GIF sono fastidiose, non esitare a rimuoverle dalla risposta ei visitatori possono anche ottenere il codice sorgente della demo live da BranchPredictorDemo
|
Guadagno di previsione del ramo!
È importante capire che la previsione errata del ramo non rallenta i programmi. Il costo di una previsione mancata è come se la previsione del ramo non esistesse e si aspettasse la valutazione dell'espressione per decidere quale codice eseguire (ulteriori spiegazioni nel paragrafo successivo).
if (espressione)
{
// Esegui 1
} altro {
// Esegui 2
}
Ogni volta che c'è un'istruzione if-else \ switch, l'espressione deve essere valutata per determinare quale blocco deve essere eseguito. Nel codice assembly generato dal compilatore vengono inserite le istruzioni del ramo condizionale.
Un'istruzione di ramo può far sì che un computer inizi a eseguire una sequenza di istruzioni diversa e quindi deviare dal suo comportamento predefinito di eseguire le istruzioni in ordine (cioè se l'espressione è falsa, il programma salta il codice del blocco if) a seconda di una condizione, che è l'espressione valutazione nel nostro caso.
Detto questo, il compilatore cerca di prevedere il risultato prima che venga effettivamente valutato. Recupererà le istruzioni dal blocco if, e se l'espressione risulta essere vera, allora meraviglioso! Abbiamo guadagnato il tempo necessario per valutarlo e fatto progressi nel codice; in caso contrario, stiamo eseguendo il codice sbagliato, la pipeline viene svuotata e viene eseguito il blocco corretto.
Visualizzazione:
Supponiamo che tu debba scegliere il percorso 1 o il percorso 2. In attesa che il tuo partner controlli la mappa, ti sei fermato al ## e hai aspettato, oppure potresti semplicemente scegliere il percorso 1 e se sei stato fortunato (il percorso 1 è il percorso corretto), poi fantastico non hai dovuto aspettare che il tuo partner controllasse la mappa (hai risparmiato il tempo che gli sarebbe servito per controllare la mappa), altrimenti tornerai indietro.
Sebbene lo svuotamento delle condutture sia super veloce, oggi vale la pena scommettere. Prevedere dati ordinati o dati che cambiano lentamente è sempre più facile e migliore che prevedere cambiamenti rapidi.
O Itinerario 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
Itinerario 2 \ --------------------------------
|
Su ARM, non è necessario alcun ramo, perché ogni istruzione ha un campo condizione a 4 bit, che verifica (a costo zero) una qualsiasi delle 16 diverse condizioni che possono verificarsi nel registro di stato del processore e se la condizione su un'istruzione è false, l'istruzione viene saltata. Ciò elimina la necessità di rami corti e non ci sarebbe alcun successo nella previsione dei rami per questo algoritmo. Pertanto, la versione ordinata di questo algoritmo verrebbe eseguita più lentamente rispetto alla versione non ordinata su ARM, a causa del sovraccarico aggiuntivo dell'ordinamento.
Il ciclo interno per questo algoritmo sarebbe simile al seguente in linguaggio assembly ARM:
MOV R0, # 0 // R0 = somma = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, data // R2 = addr of data array (metti questa istruzione fuori dal loop esterno)
.inner_loop // Etichetta del ramo del loop interno
LDRB R3, [R2, R1] // R3 = dati [c]
CMP R3, # 128 // confronta R3 con 128
AGGIUNGI R0, R0, R3 // se R3> = 128, quindi somma + = dati [c] - nessun ramo necessario!
AGGIUNGI R1, R1, # 1 // c ++
CMP R1, #arraySize // confronta c con arraySize
BLT inner_loop // Vai a inner_loop se c  ());
for (unsigned c = 0; c  = 128
somma = somma + dati1 (j);
fine
fine
fine
toc;
ExeTimeWithSorting = toc - tic;
I risultati per il codice MATLAB di cui sopra sono i seguenti:
a: Tempo trascorso (senza ordinamento) = 3479,880861 secondi.
b: Tempo trascorso (con ordinamento) = 2377,873098 secondi.
I risultati del codice C come in @GManNickG ottengo:
a: Tempo trascorso (senza ordinamento) = 19,8761 sec.
b: Tempo trascorso (con ordinamento) = 7,37778 sec.
Sulla base di ciò, sembra che MATLAB sia quasi 175 volte più lento dell'implementazione C senza l'ordinamento e 350 volte più lento con l'ordinamento. In altre parole, l'effetto (della predizione del ramo) è 1,46x per l'implementazione di MATLAB e 2,7x per l'implementazione C.
|
L'ipotesi di altre risposte che è necessario ordinare i dati non è corretta.
Il codice seguente non ordina l'intero array, ma solo i suoi segmenti di 200 elementi e quindi viene eseguito il più veloce.
L'ordinamento delle sole sezioni di elementi k completa la pre-elaborazione in tempo lineare, O (n), anziché O (n.log (n)) tempo necessario per ordinare l'intero array.
#include 
#include 
#include 
int main () {
dati int [32768]; const int l = dimensione dei dati / dimensione dei dati [0];
for (unsigned c = 0; c  = 128)
somma + = dati [c];
}
}
std :: cout << static_cast  (clock () - start) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << sum << std :: endl;
}
Questo "dimostra" anche che non ha nulla a che fare con alcun problema algoritmico come l'ordinamento, ed è effettivamente la previsione dei rami.
|
La risposta di Bjarne Stroustrup a questa domanda:
Sembra una domanda da intervista. È vero? Come lo sapresti? È una cattiva idea rispondere a domande sull'efficienza senza prima effettuare alcune misurazioni, quindi è importante sapere come misurare.
Quindi, ho provato con un vettore di un milione di numeri interi e ho ottenuto:
Già ordinato 32995 millisecondi
125944 millisecondi mescolati
Già ordinato 18610 millisecondi
133304 millisecondi mescolati
Già ordinato 17942 millisecondi
107858 millisecondi mescolati
L'ho eseguito un paio di volte per essere sicuro. Sì, il fenomeno è reale. Il mio codice chiave era:
void run (vettore  & v, const string & label)
{
auto t0 = system_clock :: now ();
sort (v.begin (), v.end ());
auto t1 = system_clock :: now ();
cout << etichetta
<< duration_cast  (t1 - t0) .count ()
<< "millisecondi \ n";
}
void tst ()
{
vettore  v (1'000'000);
iota (v.begin (), v.end (), 0);
run (v, "già ordinato");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
run (v, "shuffled");
}
Almeno il fenomeno è reale con questo compilatore, libreria standard e impostazioni di ottimizzazione. Implementazioni differenti possono dare e danno risposte differenti. In effetti, qualcuno ha fatto uno studio più sistematico (una rapida ricerca sul web lo troverà) e la maggior parte delle implementazioni mostra quell'effetto.
Uno dei motivi è la previsione del ramo: l'operazione chiave nell'algoritmo di ordinamento è "if (v [i]  = 128. Ciò significa che possiamo facilmente estrarre un singolo bit che ci dirà se vogliamo o meno un valore: spostando i dati a destra 7 bit, ci rimane uno 0 bit o un 1 bit, e vogliamo solo aggiungere il valore quando abbiamo un 1 bit. Chiamiamo questo bit "bit decisionale".
Usando il valore 0/1 del bit decisionale come indice in un array, possiamo creare codice che sarà altrettanto veloce indipendentemente dal fatto che i dati siano ordinati o meno. Il nostro codice aggiungerà sempre un valore, ma quando il bit di decisione è 0, aggiungeremo il valore da qualche parte non ci interessa. Ecco il codice:
// Test
clock_t start = clock ();
lungo lungo a [] = {0, 0};
somma lunga lunga;
for (unsigned i = 0; i <100000; ++ i)
{
// Ciclo primario
for (unsigned c = 0; c > 7);
a [j] + = dati [c];
}
}
double elapsedTime = static_cast  (clock () - start) / CLOCKS_PER_SEC;
somma = a [1];
Questo codice spreca metà delle aggiunte ma non ha mai un errore di previsione del ramo. È tremendamente più veloce su dati casuali rispetto alla versione con un'istruzione if effettiva.
Ma nei miei test, una tabella di ricerca esplicita era leggermente più veloce di questa, probabilmente perché l'indicizzazione in una tabella di ricerca era leggermente più veloce dello spostamento di bit. Questo mostra come il mio codice imposta e utilizza la tabella di ricerca (chiamata senza fantasia lut per "Tabella di ricerca" nel codice). Ecco il codice C ++:
// Dichiara e quindi compila la tabella di ricerca
int lut [256];
for (unsigned c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Usa la tabella di ricerca dopo che è stata creata
for (unsigned i = 0; i <100000; ++ i)
{
// Ciclo primario
for (unsigned c = 0; c  valore)
node = node-> pLeft;
altro
node = node-> pRight;
questa libreria farebbe qualcosa di simile:
i = (x  valore);
nodo = nodo-> collegamento [i];
È una bella soluzione e forse funzionerà.
|
Domanda molto attiva. Guadagna 10 punti reputazione per rispondere a questa domanda. Il requisito di reputazione aiuta a proteggere questa domanda dallo spam e dalle attività di mancata risposta.
Non è la risposta che stai cercando? Sfoglia altre domande contrassegnate con java c ++ ottimizzazione delle prestazioni branch-prediction o fai la tua domanda.